//非递归快速排序算法
//借助栈来实现非递归快速排序。
// by azjiao
// 2021.10.27
#include "QuickSort.h"

/** \brief 分区数列中轴数移动，数列相对中轴数大致有序。
 * \brief 实现中轴数定位，中轴数左边数列均小于等于中轴数，右边均大于中轴数。
 *
 * \param
 * \param
 * \return 中轴数在数列中的索引。
 *
 */

int partAxisMove(int aData[], int iL, int iR) {
	//取得中轴数，这里为第左界数。
	int iAxis = aData[iL];

	//如果左右界不重合就循环移动数据。
	while (iL < iR) {
		//从右界向左寻找小于等于中轴数的单元。
		while ((iL < iR) && (aData[iR] > iAxis))
			iR--;

		if (iL < iR) {
			//用右界元素覆盖左界元素。
			aData[iL] = aData[iR];
			iL++; //左界右移一个单元。
		}

		//从左界向右寻找大于中轴数的单元。
		while ((iL < iR) && (aData[iL] <= iAxis)) {
			iL++;
		}

		if(iL < iR) {
			//用左界元素覆盖右界元素。
			aData[iR] = aData[iL];
			iR--; //右界左移一个单元。
		}
	}

	//iL和iR重合，iL就是中轴位置。
	//用中轴数覆盖iL位置数。
	aData[iL] = iAxis;
	return iL; //返回中轴索引。
}

/** \brief 借助栈实现非递归的快速排序。
 *
 * \param iLBorder,iRBorder:左右界索引。
 * \param
 * \return
 *
 */

void quickSort_NotRec(int aData[], int iLBorder, int iRBorder) {
	if (iLBorder < iRBorder) {
		typeStackElem e;
		initStack();

		//进行一次中轴数移动，确定中轴定位点，以便左右分区。
		int iAxisIndex = partAxisMove(aData, iLBorder, iRBorder);

		//判断是否存在右分区。
		if (iAxisIndex < iRBorder) {
			//把右分区界压栈
			e.iL = iAxisIndex + 1;
			e.iR = iRBorder;
			push(e);
		}

		//判断是否存在左分区。
		if (iAxisIndex > iLBorder) {
			//把左分区界压栈
			e.iL = iLBorder;
			e.iR = iAxisIndex - 1;
			push(e);
		}

		//如果栈不空，则继续循环操作。
		while (0 == isEmpty()) {
			//弹栈一个分区获取分界数据.
			e = pop();
			int iL = e.iL;
			int iR = e.iR;
			//进行一次中轴数移动，确定中轴定位点。
			iAxisIndex = partAxisMove(aData, iL, iR);
			//判断是否存在右分区。
			if (iAxisIndex < iR) {
				//把右分区界压栈
				e.iL = iAxisIndex + 1;
				e.iR = iR;
				push(e);
			}

			//判断是否存在左分区。
			if (iAxisIndex > iL) {
				//把左分区界压栈
				e.iL = iL;
				e.iR = iAxisIndex - 1;
				push(e);
			}
		}

	}
}

//非递归快速排序调试版。
void quickSort_NotRec_Test(int aData[], int iLBorder, int iRBorder) {
	if (iLBorder < iRBorder) {
		typeStackElem e;
		initStack();

        printStack();

		//进行一次中轴数移动，确定中轴定位点，以便左右分区。
		int iAxisIndex = partAxisMove(aData, iLBorder, iRBorder);
		printArry(aData, iLBorder, iRBorder-iLBorder+1, iLBorder, iRBorder, -1, iAxisIndex);

		//判断是否存在右分区。
		if (iAxisIndex < iRBorder) {
			//把右分区界压栈
			e.iL = iAxisIndex + 1;
			e.iR = iRBorder;
			push(e);
			printf("push\n");
			printStack();
		}

		//判断是否存在左分区。
		if (iAxisIndex > iLBorder) {
			//把左分区界压栈
			e.iL = iLBorder;
			e.iR = iAxisIndex - 1;
			push(e);
			printf("push\n");
			printStack();
		}

		//如果栈不空，则继续循环操作。
		while (0 == isEmpty()) {
			//弹栈一个分区获取分界数据.
			e = pop();
			printf("pop\n");
			printStack();
			int iL = e.iL;
			int iR = e.iR;
			//进行一次中轴数移动，确定中轴定位点。
			iAxisIndex = partAxisMove(aData, iL, iR);
			printArry(aData, iLBorder, iRBorder-iLBorder+1, iLBorder, iRBorder, -1, iAxisIndex);
			//判断是否存在右分区。
			if (iAxisIndex < iR) {
				//把右分区界压栈
				e.iL = iAxisIndex + 1;
				e.iR = iR;
				push(e);
				printf("push\n");
				printStack();
			}

			//判断是否存在左分区。
			if (iAxisIndex > iL) {
				//把左分区界压栈
				e.iL = iL;
				e.iR = iAxisIndex - 1;
				push(e);
				printf("push\n");
				printStack();
			}
		}

	}
}
